package day_2022_9_to_12.Day;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author haomin
 * @date 2022/09/29 22:41
 **/
public class Day28_7_Offer49_NthUglyNumber {
    class Solution {
        public int nthUglyNumber(int n) {
            int[] dp = new int[n];
            dp[0] = 1;
            int res, ind2 = 0, ind3 = 0, ind5 = 0;
            for(int i = 1; i < n; ++i){
                res = Math.min(dp[ind2] * 2, Math.min(dp[ind3] * 3, dp[ind5] * 5));
                if(res % 2 == 0) ind2++;
                if(res % 3 == 0) ind3++;
                if(res % 5 == 0) ind5++;
                dp[i] = res;
            }
            return dp[n-1];
        }
    }

    class Solution2 {
        public int nthUglyNumber(int n) {
            long cur = 1, count = 0;
            List<Long> list = new ArrayList<>();
            Queue<Long> q = new PriorityQueue<>();
            q.add(cur);
            while(!q.isEmpty()){
                cur = q.poll();
                if(!list.contains(cur)){
                    q.add(cur * 2);
                    q.add(cur * 3);
                    q.add(cur * 5);
                    list.add(cur);
                    if(++count == n) break;
                }
            }
            return (int)cur;
        }
    }
}